package main

import (
	"strconv"
	"strings"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type Codec struct {
	sequence string
	nodes    []string
}

func Constructor() Codec {
	return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
	this.sequence = ""
	this.doSerialize(root)
	return this.sequence
}

func (this *Codec) doSerialize(root *TreeNode) {
	if root == nil {
		this.sequence += ",#"
		return
	}
	this.sequence += "," + strconv.Itoa(root.Val)
	this.doSerialize(root.Left)
	this.doSerialize(root.Right)
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
	this.nodes = strings.Split(data, ",")[1:]
	return this.doDeserialize()
}

func (this *Codec) doDeserialize() *TreeNode {
	if len(this.nodes) == 0 {
		return nil
	}
	if this.nodes[0] == "#" {
		this.nodes = this.nodes[1:]
		return nil
	}
	val, _ := strconv.Atoi(this.nodes[0])
	root := &TreeNode{Val: val}
	this.nodes = this.nodes[1:]
	root.Left = this.doDeserialize()
	root.Right = this.doDeserialize()
	return root
}

func main() {
	n1 := &TreeNode{Val: 1}
	n2 := &TreeNode{Val: 2}
	n3 := &TreeNode{Val: 3}
	n4 := &TreeNode{Val: 4}
	n5 := &TreeNode{Val: 5}
	n1.Left = n2
	n1.Right = n3
	n3.Left = n4
	n3.Right = n5
	c := Constructor()
	seq := c.serialize(n1)
	println(seq)
	root := c.deserialize(seq)
	println(root)
}
